//
// Created by denglibin on 2020/6/24.
//

#include "../header/sort.h"
#include <stdlib.h>

/**
 * 合并两个已排好序的数组
 * @param arr  数组
 * @param start1  第一个排好序子数组的第一个元素位置
 * @param end1 第一个排好序子数组的第一个元素位置
 * @param start2 第二个排好序子数组的第一个元素位置
 * @param end2 第二个排好序子数组的第一个元素位置
 */
static void merge_arr(int arr[], int start1, int end1, int start2, int end2){
    int tempStart1 = start1;
    int index = 0;
    int len = end1 - start1 + end2 - start2 + 2;
    int * tempArr = (int*)calloc(len, sizeof(int ));
    while (start1 <= end1 && start2 <= end2){
        if(arr[start1] < arr[start2]){
            tempArr[index++] = arr[start1++];
        } else {
            tempArr[index++] = arr[start2++];
        }
    }
    while (start1 <= end1){
        tempArr[index++] = arr[start1++];
    }
    while (start2 <= end2){
        tempArr[index++] = arr[start2++];
    }
    for(index = tempStart1; index <= end2; index++){
        arr[index] = tempArr[index - tempStart1];
    }
    free(tempArr);

}

static void do_merge_sort(int arr[], int start, int end){
    if(start < end){
        int middle = start + end;
        middle /= 2;
        do_merge_sort(arr, start, middle); // 排序左边
        do_merge_sort(arr, middle + 1, end); // 排序右边
        merge_arr(arr, start, middle, middle+1, end); // 合并
    }

}
/**
 * 归并排序
 * @param arr
 * @param len
 */
static void merge_sort(int arr[], int len){
   do_merge_sort(arr, 0, len - 1);

}

int main4_sort(){
    int arr[5] = {3, 4, 5, 1, 2};
    merge_sort(arr, 5);
    print_arr(arr, 5);
    return 0;
}